package mo.offer_special;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class L110 {

    private List<List<Integer>> ret = new ArrayList<>();
    private Stack<Integer> queue = new Stack<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length - 1;
        queue.push(0);
        dfs(graph, 0, n);
        return ret;
    }

    private void dfs(int[][] graph, int x, int n) {
        if (x == n) {
            ret.add(new ArrayList<>(queue));
            return;
        }
        for (int next : graph[x]) {
            queue.push(next);
            dfs(graph, next, n);
            queue.pop();
        }
    }

}
